package com.leetcode.listnode.demo5;

/**
 * @Author Zan
 * @Create 2024/5/13 16:41
 * @ClassName: Test
 * @Description : https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/   删除链表的倒数第 N 个结点
 */
public class Test {
    public static void main(String[] args) {

    }
}

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return head;
        }
        // 使用双指针的想法，走得快的每次都有n+1步，将中间那一块空出来
        // 这样子当走得快走到了最后，就可以进行删除了
        ListNode dummy = new ListNode();
        dummy.next = head;

        ListNode fastNode = dummy;
        ListNode slowNode = dummy;

        // fast要先走n+1，然后再一起走
        int newN = n + 1;
        while (newN-- > 0) {
            fastNode = fastNode.next;
        }

        while (fastNode != null) {
            fastNode = fastNode.next;
            slowNode = slowNode.next;
        }
        slowNode.next = slowNode.next.next;
        return dummy.next;
    }
}

class ListNode {
    int val;
    ListNode next;

    public ListNode() {
    }
    public ListNode(int val) {
        this.val = val;
    }
    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}